home *** CD-ROM | disk | FTP | other *** search
/ PC PowerPlay 58 / pcpp58a.iso / extras / quake 3 source / Q3A_ToolSource.exe / Main / surface.c < prev    next >
Encoding:
C/C++ Source or Header  |  2001-01-02  |  27.9 KB  |  1,134 lines
  1.  
  2. #include "qbsp.h"
  3.  
  4.  
  5. mapDrawSurface_t    mapDrawSurfs[MAX_MAP_DRAW_SURFS];
  6. int            numMapDrawSurfs;
  7.  
  8. /*
  9. =============================================================================
  10.  
  11. DRAWSURF CONSTRUCTION
  12.  
  13. =============================================================================
  14. */
  15.  
  16. /*
  17. =================
  18. AllocDrawSurf
  19. =================
  20. */
  21. mapDrawSurface_t    *AllocDrawSurf( void ) {
  22.     mapDrawSurface_t    *ds;
  23.  
  24.     if ( numMapDrawSurfs >= MAX_MAP_DRAW_SURFS ) {
  25.         Error( "MAX_MAP_DRAW_SURFS");
  26.     }
  27.     ds = &mapDrawSurfs[ numMapDrawSurfs ];
  28.     numMapDrawSurfs++;
  29.  
  30.     return ds;
  31. }
  32.  
  33. /*
  34. =================
  35. DrawSurfaceForSide
  36. =================
  37. */
  38. #define    SNAP_FLOAT_TO_INT    8
  39. #define    SNAP_INT_TO_FLOAT    (1.0/SNAP_FLOAT_TO_INT)
  40.  
  41. mapDrawSurface_t    *DrawSurfaceForSide( bspbrush_t *b, side_t *s, winding_t *w ) {
  42.     mapDrawSurface_t    *ds;
  43.     int                    i, j;
  44.     shaderInfo_t        *si;
  45.     drawVert_t            *dv;
  46.     float                mins[2], maxs[2];
  47.  
  48.     // brush primitive :
  49.     // axis base
  50.     vec3_t        texX,texY;
  51.     vec_t        x,y;
  52.  
  53.     if ( w->numpoints > 64 ) {
  54.         Error( "DrawSurfaceForSide: w->numpoints = %i", w->numpoints );
  55.     }
  56.  
  57.     si = s->shaderInfo;
  58.  
  59.     ds = AllocDrawSurf();
  60.  
  61.     ds->shaderInfo = si;
  62.     ds->mapBrush = b;
  63.     ds->side = s;
  64.     ds->fogNum = -1;
  65.     ds->numVerts = w->numpoints;
  66.     ds->verts = malloc( ds->numVerts * sizeof( *ds->verts ) );
  67.     memset( ds->verts, 0, ds->numVerts * sizeof( *ds->verts ) );
  68.  
  69.     mins[0] = mins[1] = 99999;
  70.     maxs[0] = maxs[1] = -99999;
  71.  
  72.     // compute s/t coordinates from brush primitive texture matrix
  73.     // compute axis base
  74.     ComputeAxisBase( mapplanes[s->planenum].normal, texX, texY );
  75.  
  76.     for ( j = 0 ; j < w->numpoints ; j++ ) {
  77.         dv = ds->verts + j;
  78.  
  79.         // round the xyz to a given precision
  80.         for ( i = 0 ; i < 3 ; i++ ) {
  81.             dv->xyz[i] = SNAP_INT_TO_FLOAT * floor( w->p[j][i] * SNAP_FLOAT_TO_INT + 0.5 );
  82.         }
  83.     
  84.         if (g_bBrushPrimit==BPRIMIT_OLDBRUSHES)
  85.         {
  86.             // calculate texture s/t
  87.             dv->st[0] = s->vecs[0][3] + DotProduct( s->vecs[0],    dv->xyz );
  88.             dv->st[1] = s->vecs[1][3] + DotProduct( s->vecs[1],    dv->xyz );
  89.             dv->st[0] /= si->width;
  90.             dv->st[1] /= si->height;
  91.         } 
  92.         else
  93.         {
  94.             // calculate texture s/t from brush primitive texture matrix
  95.             x = DotProduct( dv->xyz, texX );
  96.             y = DotProduct( dv->xyz, texY );
  97.             dv->st[0]=s->texMat[0][0]*x+s->texMat[0][1]*y+s->texMat[0][2];
  98.             dv->st[1]=s->texMat[1][0]*x+s->texMat[1][1]*y+s->texMat[1][2];
  99.         }
  100.  
  101.         for ( i = 0 ; i < 2 ; i++ ) {
  102.             if ( dv->st[i] < mins[i] ) {
  103.                 mins[i] = dv->st[i];
  104.             }
  105.             if ( dv->st[i] > maxs[i] ) {
  106.                 maxs[i] = dv->st[i];
  107.             }
  108.         }
  109.  
  110.         // copy normal
  111.         VectorCopy ( mapplanes[s->planenum].normal, dv->normal );
  112.     }
  113.  
  114.     // adjust the texture coordinates to be as close to 0 as possible
  115.     if ( !si->globalTexture ) {
  116.         mins[0] = floor( mins[0] );
  117.         mins[1] = floor( mins[1] );
  118.         for ( i = 0 ; i < w->numpoints ; i++ ) {
  119.             dv = ds->verts + i;
  120.             dv->st[0] -= mins[0];
  121.             dv->st[1] -= mins[1];
  122.         }
  123.     }
  124.  
  125.     return ds;
  126. }
  127.  
  128.  
  129. //=========================================================================
  130.  
  131.  
  132.  
  133.  
  134. typedef struct {
  135.     int                planenum;
  136.     shaderInfo_t    *shaderInfo;
  137.     int                count;
  138. } sideRef_t;
  139.  
  140. #define    MAX_SIDE_REFS    MAX_MAP_PLANES
  141.  
  142. sideRef_t    sideRefs[MAX_SIDE_REFS];
  143. int            numSideRefs;
  144.  
  145. void AddSideRef( side_t *side ) {
  146.     int        i;
  147.  
  148.     for ( i = 0 ; i < numSideRefs ; i++ ) {
  149.         if ( side->planenum == sideRefs[i].planenum
  150.             && side->shaderInfo == sideRefs[i].shaderInfo ) {
  151.             sideRefs[i].count++;
  152.             return;
  153.         }
  154.     }
  155.  
  156.     if ( numSideRefs == MAX_SIDE_REFS ) {
  157.         Error( "MAX_SIDE_REFS" );
  158.     }
  159.  
  160.     sideRefs[i].planenum = side->planenum;
  161.     sideRefs[i].shaderInfo = side->shaderInfo;
  162.     sideRefs[i].count++;
  163.     numSideRefs++;
  164. }
  165.  
  166.  
  167. /*
  168. =====================
  169. MergeSides
  170.  
  171. =====================
  172. */
  173. void MergeSides( entity_t *e, tree_t *tree ) {
  174.     int                i;
  175.  
  176.     qprintf( "----- MergeSides -----\n");
  177.  
  178.     for ( i = e->firstDrawSurf ; i < numMapDrawSurfs ; i++ ) {
  179. //            AddSideRef( side );
  180.     }
  181.  
  182.     qprintf( "%5i siderefs\n", numSideRefs );
  183. }
  184.  
  185. //=====================================================================
  186.  
  187. /*
  188. ===================
  189. SubdivideDrawSurf
  190. ===================
  191. */
  192. void SubdivideDrawSurf( mapDrawSurface_t *ds, winding_t *w, float subdivisions ) {
  193.     int                i;
  194.     int                axis;
  195.     vec3_t            bounds[2];
  196.     const float        epsilon = 0.1;
  197.     int                subFloor, subCeil;
  198.     winding_t        *frontWinding, *backWinding;
  199.     mapDrawSurface_t    *newds;
  200.  
  201.     if ( !w ) {
  202.         return;
  203.     }
  204.     if ( w->numpoints < 3 ) {
  205.         Error( "SubdivideDrawSurf: Bad w->numpoints" );
  206.     }
  207.  
  208.     ClearBounds( bounds[0], bounds[1] );
  209.     for ( i = 0 ; i < w->numpoints ; i++ ) {
  210.         AddPointToBounds( w->p[i], bounds[0], bounds[1] );
  211.     }
  212.  
  213.     for ( axis = 0 ; axis < 3 ; axis++ ) {
  214.         vec3_t planePoint = { 0, 0, 0 };
  215.         vec3_t planeNormal = { 0, 0, 0 };
  216.         float d;
  217.  
  218.         subFloor = floor( bounds[0][axis]  / subdivisions ) * subdivisions;
  219.         subCeil = ceil( bounds[1][axis] / subdivisions ) * subdivisions;
  220.  
  221.         planePoint[axis] = subFloor + subdivisions;
  222.         planeNormal[axis] = -1;
  223.  
  224.         d = DotProduct( planePoint, planeNormal );
  225.  
  226.         // subdivide if necessary
  227.         if ( subCeil - subFloor > subdivisions ) {
  228.             // gotta clip polygon into two polygons
  229.             ClipWindingEpsilon( w, planeNormal, d, epsilon, &frontWinding, &backWinding );
  230.  
  231.             // the clip may not produce two polygons if it was epsilon close
  232.             if ( !frontWinding ) {
  233.                 w = backWinding;
  234.             } else if ( !backWinding ) {
  235.                 w = frontWinding;
  236.             } else {
  237.                 SubdivideDrawSurf( ds, frontWinding, subdivisions );
  238.                 SubdivideDrawSurf( ds, backWinding, subdivisions );
  239.  
  240.                 return;
  241.             }
  242.         }
  243.     }
  244.  
  245.     // emit this polygon
  246.     newds = DrawSurfaceForSide( ds->mapBrush, ds->side, w );
  247.     newds->fogNum = ds->fogNum;
  248. }
  249.  
  250.  
  251. /*
  252. =====================
  253. SubdivideDrawSurfs
  254.  
  255. Chop up surfaces that have subdivision attributes
  256. =====================
  257. */
  258. void SubdivideDrawSurfs( entity_t *e, tree_t *tree ) {
  259.     int                i;
  260.     mapDrawSurface_t    *ds;
  261.     int                numBaseDrawSurfs;
  262.     winding_t        *w;
  263.     float            subdivision;
  264.     shaderInfo_t    *si;
  265.  
  266.     qprintf( "----- SubdivideDrawSurfs -----\n");
  267.     numBaseDrawSurfs = numMapDrawSurfs;
  268.     for ( i = e->firstDrawSurf ; i < numBaseDrawSurfs ; i++ ) {
  269.         ds = &mapDrawSurfs[i];
  270.  
  271.         // only subdivide brush sides, not patches or misc_models
  272.         if ( !ds->side ) {
  273.             continue;
  274.         }
  275.  
  276.         // check subdivision for shader
  277.         si = ds->side->shaderInfo;
  278.         if ( !si ) {
  279.             continue;
  280.         }
  281.  
  282.         if (ds->shaderInfo->autosprite || si->autosprite) {
  283.             continue;
  284.         }
  285.  
  286.         subdivision = si->subdivisions;
  287.         if ( !subdivision ) {
  288.             continue;
  289.         }
  290.  
  291.         w = WindingFromDrawSurf( ds );
  292.         ds->numVerts = 0;        // remove this reference
  293.         SubdivideDrawSurf( ds, w, subdivision );
  294.     }
  295.  
  296. }
  297.  
  298.  
  299. //===================================================================================
  300.  
  301. /*
  302. ====================
  303. ClipSideIntoTree_r
  304.  
  305. Adds non-opaque leaf fragments to the convex hull
  306. ====================
  307. */
  308. void ClipSideIntoTree_r( winding_t *w, side_t *side, node_t *node ) {
  309.     plane_t            *plane;
  310.     winding_t        *front, *back;
  311.  
  312.     if ( !w ) {
  313.         return;
  314.     }
  315.  
  316.     if ( node->planenum != PLANENUM_LEAF ) {
  317.         if ( side->planenum == node->planenum ) {
  318.             ClipSideIntoTree_r( w, side, node->children[0] );
  319.             return;
  320.         }
  321.         if ( side->planenum == ( node->planenum ^ 1) ) {
  322.             ClipSideIntoTree_r( w, side, node->children[1] );
  323.             return;
  324.         }
  325.  
  326.         plane = &mapplanes[ node->planenum ];
  327.         ClipWindingEpsilon ( w, plane->normal, plane->dist,
  328.                 ON_EPSILON, &front, &back );
  329.         FreeWinding( w );
  330.  
  331.         ClipSideIntoTree_r( front, side, node->children[0] );
  332.         ClipSideIntoTree_r( back, side, node->children[1] );
  333.  
  334.         return;
  335.     }
  336.  
  337.     // if opaque leaf, don't add
  338.     if ( !node->opaque ) {
  339.         AddWindingToConvexHull( w, &side->visibleHull, mapplanes[ side->planenum ].normal );
  340.     }
  341.  
  342.     FreeWinding( w );
  343.     return;
  344. }
  345.  
  346.  
  347. /*
  348. =====================
  349. ClipSidesIntoTree
  350.  
  351. Creates side->visibleHull for all visible sides
  352.  
  353. The drawsurf for a side will consist of the convex hull of
  354. all points in non-opaque clusters, which allows overlaps
  355. to be trimmed off automatically.
  356. =====================
  357. */
  358. void ClipSidesIntoTree( entity_t *e, tree_t *tree ) {
  359.     bspbrush_t        *b;
  360.     int                i;
  361.     winding_t        *w;
  362.     side_t            *side, *newSide;
  363.     shaderInfo_t    *si;
  364.  
  365.     qprintf( "----- ClipSidesIntoTree -----\n");
  366.  
  367.     for ( b = e->brushes ; b ; b = b->next ) {
  368.         for ( i = 0 ; i < b->numsides ; i++ ) {
  369.             side = &b->sides[i];
  370.             if ( !side->winding) {
  371.                 continue;
  372.             }
  373.             w = CopyWinding( side->winding );
  374.             side->visibleHull = NULL;
  375.             ClipSideIntoTree_r( w, side, tree->headnode );
  376.  
  377.             w = side->visibleHull;
  378.             if ( !w ) {
  379.                 continue;
  380.             }
  381.             si = side->shaderInfo;
  382.             if ( !si ) {
  383.                 continue;
  384.             }
  385.             // don't create faces for non-visible sides
  386.             if ( si->surfaceFlags & SURF_NODRAW ) {
  387.                 continue;
  388.             }
  389.  
  390.             // always use the original quad winding for auto sprites
  391.             if ( side->shaderInfo->autosprite ) {
  392.                 w = side->winding;
  393.             }
  394.             // save this winding as a visible surface
  395.             DrawSurfaceForSide( b, side, w );
  396.  
  397.             // make a back side for it if needed
  398.             if ( !(si->contents & CONTENTS_FOG) ) {
  399.                 continue;
  400.             }
  401.  
  402.             // duplicate the up-facing side
  403.             w = ReverseWinding( w );
  404.         
  405.             newSide = malloc( sizeof( *side ) );
  406.             *newSide = *side;
  407.             newSide->visibleHull = w;
  408.             newSide->planenum ^= 1;
  409.  
  410.             // save this winding as a visible surface
  411.             DrawSurfaceForSide( b, newSide, w );
  412.  
  413.         }
  414.     }
  415. }
  416.  
  417. /*
  418. ===================================================================================
  419.  
  420.   FILTER REFERENCES DOWN THE TREE
  421.  
  422. ===================================================================================
  423. */
  424.  
  425. /*
  426. ====================
  427. FilterDrawSurfIntoTree
  428.  
  429. Place a reference to the given drawsurf in every leaf it contacts
  430. We assume that the point mesh aproximation to the curve will get a 
  431. reference into all the leafs we need.
  432. ====================
  433. */
  434. int FilterMapDrawSurfIntoTree( vec3_t point, mapDrawSurface_t *ds, node_t *node ) {
  435.     drawSurfRef_t    *dsr;
  436.     float            d;
  437.     plane_t            *plane;
  438.     int                c;
  439.  
  440.     if ( node->planenum != PLANENUM_LEAF ) {
  441.         plane = &mapplanes[ node->planenum ];
  442.         d = DotProduct( point, plane->normal ) - plane->dist;
  443.         c = 0;
  444.         if ( d >= -ON_EPSILON ) {
  445.             c += FilterMapDrawSurfIntoTree( point, ds, node->children[0] );
  446.         }
  447.         if ( d <= ON_EPSILON ) {
  448.             c += FilterMapDrawSurfIntoTree( point, ds, node->children[1] );
  449.         }
  450.         return c;
  451.     }
  452.  
  453.     // if opaque leaf, don't add
  454.     if ( node->opaque ) {
  455.         return 0;
  456.     }
  457.  
  458.     // add the drawsurf if it hasn't been already
  459.     for ( dsr = node->drawSurfReferences ; dsr ; dsr = dsr->nextRef ) {
  460.         if ( dsr->outputNumber == numDrawSurfaces ) {
  461.             return 0;        // already referenced
  462.         }
  463.     }
  464.  
  465.     dsr = malloc( sizeof( *dsr ) );
  466.     dsr->outputNumber = numDrawSurfaces;
  467.     dsr->nextRef = node->drawSurfReferences;
  468.     node->drawSurfReferences = dsr;
  469.     return 1;
  470. }
  471.  
  472. /*
  473. ====================
  474. FilterDrawSurfIntoTree_r
  475.  
  476. Place a reference to the given drawsurf in every leaf it is in
  477. ====================
  478. */
  479. int FilterMapDrawSurfIntoTree_r( winding_t *w, mapDrawSurface_t *ds, node_t *node ) {
  480.     drawSurfRef_t    *dsr;
  481.     plane_t            *plane;
  482.     int                total;
  483.     winding_t        *front, *back;
  484.  
  485.     if ( node->planenum != PLANENUM_LEAF ) {
  486.         plane = &mapplanes[ node->planenum ];
  487.         ClipWindingEpsilon ( w, plane->normal, plane->dist,
  488.                 ON_EPSILON, &front, &back );
  489.  
  490.         total = 0;
  491.         if ( front ) {
  492.             total += FilterMapDrawSurfIntoTree_r( front, ds, node->children[0] );
  493.         }
  494.         if ( back ) {
  495.             total += FilterMapDrawSurfIntoTree_r( back, ds, node->children[1] );
  496.         }
  497.  
  498.         FreeWinding( w );
  499.         return total;
  500.     }
  501.  
  502.     // if opaque leaf, don't add
  503.     if ( node->opaque ) {
  504.         return 0;
  505.     }
  506.  
  507.     // add the drawsurf if it hasn't been already
  508.     for ( dsr = node->drawSurfReferences ; dsr ; dsr = dsr->nextRef ) {
  509.         if ( dsr->outputNumber == numDrawSurfaces ) {
  510.             return 0;        // already referenced
  511.         }
  512.     }
  513.  
  514.     dsr = malloc( sizeof( *dsr ) );
  515.     dsr->outputNumber = numDrawSurfaces;
  516.     dsr->nextRef = node->drawSurfReferences;
  517.     node->drawSurfReferences = dsr;
  518.     return 1;
  519. }
  520.  
  521. /*
  522. ====================
  523. FilterSideIntoTree_r
  524.  
  525. Place a reference to the given drawsurf in every leaf it contacts
  526. ====================
  527. */
  528. int FilterSideIntoTree_r( winding_t *w, side_t *side, mapDrawSurface_t *ds, node_t *node ) {
  529.     drawSurfRef_t    *dsr;
  530.     plane_t            *plane;
  531.     winding_t        *front, *back;
  532.     int                total;
  533.  
  534.     if ( !w ) {
  535.         return 0;
  536.     }
  537.  
  538.     if ( node->planenum != PLANENUM_LEAF ) {
  539.         if ( side->planenum == node->planenum ) {
  540.             return FilterSideIntoTree_r( w, side, ds, node->children[0] );
  541.         }
  542.         if ( side->planenum == ( node->planenum ^ 1) ) {
  543.             return FilterSideIntoTree_r( w, side, ds, node->children[1] );
  544.         }
  545.  
  546.         plane = &mapplanes[ node->planenum ];
  547.         ClipWindingEpsilon ( w, plane->normal, plane->dist,
  548.                 ON_EPSILON, &front, &back );
  549.  
  550.         total = FilterSideIntoTree_r( front, side, ds, node->children[0] );
  551.         total += FilterSideIntoTree_r( back, side, ds, node->children[1] );
  552.  
  553.         FreeWinding( w );
  554.         return total;
  555.     }
  556.  
  557.     // if opaque leaf, don't add
  558.     if ( node->opaque ) {
  559.         return 0;
  560.     }
  561.  
  562.     dsr = malloc( sizeof( *dsr ) );
  563.     dsr->outputNumber = numDrawSurfaces;
  564.     dsr->nextRef = node->drawSurfReferences;
  565.     node->drawSurfReferences = dsr;
  566.  
  567.     FreeWinding( w );
  568.     return 1;
  569. }
  570.  
  571.  
  572. /*
  573. =====================
  574. FilterFaceIntoTree
  575. =====================
  576. */
  577. int    FilterFaceIntoTree( mapDrawSurface_t *ds, tree_t *tree ) {
  578.     int            l;
  579.     winding_t    *w;
  580.  
  581.     w = WindingFromDrawSurf( ds );
  582.     l = FilterSideIntoTree_r( w, ds->side, ds, tree->headnode );
  583.  
  584.     return l;
  585. }
  586.  
  587.  
  588.  
  589. /*
  590. =====================
  591. FilterPatchSurfIntoTree
  592. =====================
  593. */
  594. #define    SUBDIVISION_LIMIT        8.0
  595. int FilterPatchSurfIntoTree( mapDrawSurface_t *ds, tree_t *tree ) {
  596.     int                    i, j;
  597.     int                    l;
  598.     mesh_t                baseMesh, *subdividedMesh;
  599.     winding_t            *w;
  600.  
  601.     baseMesh.width = ds->patchWidth;
  602.     baseMesh.height = ds->patchHeight;
  603.     baseMesh.verts = ds->verts;
  604.     subdividedMesh = SubdivideMesh( baseMesh, SUBDIVISION_LIMIT, 32 );
  605.  
  606.     l = 0;
  607.     for (i = 0; i < subdividedMesh->width-1; i++) {
  608.         for (j = 0; j < subdividedMesh->height-1; j++) {
  609.             w = AllocWinding(3);
  610.             VectorCopy(subdividedMesh->verts[j * subdividedMesh->width + i].xyz, w->p[0]);
  611.             VectorCopy(subdividedMesh->verts[j * subdividedMesh->width + i + 1].xyz, w->p[1]);
  612.             VectorCopy(subdividedMesh->verts[(j+1) * subdividedMesh->width + i].xyz, w->p[2]);
  613.             w->numpoints = 3;
  614.             l += FilterMapDrawSurfIntoTree_r( w, ds, tree->headnode );
  615.             w = AllocWinding(3);
  616.             VectorCopy(subdividedMesh->verts[j * subdividedMesh->width + i + 1].xyz, w->p[0]);
  617.             VectorCopy(subdividedMesh->verts[(j+1) * subdividedMesh->width + i + 1].xyz, w->p[1]);
  618.             VectorCopy(subdividedMesh->verts[(j+1) * subdividedMesh->width + i].xyz, w->p[2]);
  619.             w->numpoints = 3;
  620.             l += FilterMapDrawSurfIntoTree_r( w, ds, tree->headnode );
  621.         }
  622.     }
  623.  
  624.     // also use the old point filtering into the tree
  625.     for ( i = 0 ; i < subdividedMesh->width * subdividedMesh->height ; i++ ) {
  626.         l += FilterMapDrawSurfIntoTree( subdividedMesh->verts[i].xyz, ds, tree->headnode );
  627.     }
  628.  
  629.     free(subdividedMesh);
  630.  
  631.     return l;
  632. }
  633.  
  634.  
  635. /*
  636. =====================
  637. FilterMiscModelSurfIntoTree
  638. =====================
  639. */
  640. int    FilterMiscModelSurfIntoTree( mapDrawSurface_t *ds, tree_t *tree ) {
  641.     int            i;
  642.     int            l;
  643.     winding_t *w;
  644.  
  645.     l = 0;
  646.     for (i = 0; i < ds->numIndexes-2; i++) {
  647.         w = AllocWinding(3);
  648.         VectorCopy(ds->verts[ds->indexes[i]].xyz, w->p[0]);
  649.         VectorCopy(ds->verts[ds->indexes[i+1]].xyz, w->p[1]);
  650.         VectorCopy(ds->verts[ds->indexes[i+2]].xyz, w->p[2]);
  651.         w->numpoints = 3;
  652.         l += FilterMapDrawSurfIntoTree_r( w, ds, tree->headnode );
  653.     }
  654.  
  655.     // also use the old point filtering into the tree
  656.     for ( i = 0 ; i < ds->numVerts ; i++ ) {
  657.         l += FilterMapDrawSurfIntoTree( ds->verts[i].xyz, ds, tree->headnode );
  658.     }
  659.  
  660.     return l;
  661. }
  662.  
  663. /*
  664. =====================
  665. FilterFlareSurfIntoTree
  666. =====================
  667. */
  668. int    FilterFlareSurfIntoTree( mapDrawSurface_t *ds, tree_t *tree ) {
  669.     return FilterMapDrawSurfIntoTree( ds->lightmapOrigin, ds, tree->headnode );
  670. }
  671.  
  672.  
  673. //======================================================================
  674.  
  675. int        c_stripSurfaces, c_fanSurfaces;
  676.  
  677. /*
  678. ==================
  679. IsTriangleDegenerate
  680.  
  681. Returns qtrue if all three points are collinear or backwards
  682. ===================
  683. */
  684. #define    COLINEAR_AREA    10
  685. static qboolean    IsTriangleDegenerate( drawVert_t *points, int a, int b, int c ) {
  686.     vec3_t        v1, v2, v3;
  687.     float        d;
  688.  
  689.     VectorSubtract( points[b].xyz, points[a].xyz, v1 );
  690.     VectorSubtract( points[c].xyz, points[a].xyz, v2 );
  691.     CrossProduct( v1, v2, v3 );
  692.     d = VectorLength( v3 );
  693.  
  694.     // assume all very small or backwards triangles will cause problems
  695.     if ( d < COLINEAR_AREA ) {
  696.         return qtrue;
  697.     }
  698.  
  699.     return qfalse;
  700. }
  701.  
  702. /*
  703. ===============
  704. SurfaceAsTriFan
  705.  
  706. The surface can't be represented as a single tristrip without
  707. leaving a degenerate triangle (and therefore a crack), so add
  708. a point in the middle and create (points-1) triangles in fan order
  709. ===============
  710. */
  711. static void SurfaceAsTriFan( dsurface_t *ds ) {
  712.     int                    i;
  713.     int                    colorSum[4];
  714.     drawVert_t            *mid, *v;
  715.  
  716.     // create a new point in the center of the face
  717.     if ( numDrawVerts == MAX_MAP_DRAW_VERTS ) {
  718.         Error( "MAX_MAP_DRAW_VERTS" );
  719.     }
  720.     mid = &drawVerts[ numDrawVerts ];
  721.     numDrawVerts++;
  722.  
  723.     colorSum[0] = colorSum[1] = colorSum[2] = colorSum[3] = 0;
  724.  
  725.     v = drawVerts + ds->firstVert;
  726.     for (i = 0 ; i < ds->numVerts ; i++, v++ ) {
  727.         VectorAdd( mid->xyz, v->xyz, mid->xyz );
  728.         mid->st[0] += v->st[0];
  729.         mid->st[1] += v->st[1];
  730.         mid->lightmap[0] += v->lightmap[0];
  731.         mid->lightmap[1] += v->lightmap[1];
  732.  
  733.         colorSum[0] += v->color[0];
  734.         colorSum[1] += v->color[1];
  735.         colorSum[2] += v->color[2];
  736.         colorSum[3] += v->color[3];
  737.     }
  738.  
  739.     mid->xyz[0] /= ds->numVerts;
  740.     mid->xyz[1] /= ds->numVerts;
  741.     mid->xyz[2] /= ds->numVerts;
  742.  
  743.     mid->st[0] /= ds->numVerts;
  744.     mid->st[1] /= ds->numVerts;
  745.  
  746.     mid->lightmap[0] /= ds->numVerts;
  747.     mid->lightmap[1] /= ds->numVerts;
  748.  
  749.     mid->color[0] = colorSum[0] / ds->numVerts;
  750.     mid->color[1] = colorSum[1] / ds->numVerts;
  751.     mid->color[2] = colorSum[2] / ds->numVerts;
  752.     mid->color[3] = colorSum[3] / ds->numVerts;
  753.  
  754.     VectorCopy((drawVerts+ds->firstVert)->normal, mid->normal );
  755.  
  756.     // fill in indices in trifan order
  757.     if ( numDrawIndexes + ds->numVerts*3 > MAX_MAP_DRAW_INDEXES ) {
  758.         Error( "MAX_MAP_DRAWINDEXES" );
  759.     }
  760.     ds->firstIndex = numDrawIndexes;
  761.     ds->numIndexes = ds->numVerts*3;
  762.  
  763.     //FIXME
  764.     // should be: for ( i = 0 ; i < ds->numVerts ; i++ ) {
  765.     // set a break point and test this in a map
  766.     //for ( i = 0 ; i < ds->numVerts*3 ; i++ ) {
  767.     for ( i = 0 ; i < ds->numVerts ; i++ ) {
  768.         drawIndexes[numDrawIndexes++] = ds->numVerts;
  769.         drawIndexes[numDrawIndexes++] = i;
  770.         drawIndexes[numDrawIndexes++] = (i+1) % ds->numVerts;
  771.     }
  772.  
  773.     ds->numVerts++;
  774. }
  775.  
  776.  
  777. /*
  778. ================
  779. SurfaceAsTristrip
  780.  
  781. Try to create indices that make (points-2) triangles in tristrip order
  782. ================
  783. */
  784. #define    MAX_INDICES    1024
  785. static void SurfaceAsTristrip( dsurface_t *ds ) {
  786.     int                    i;
  787.     int                    rotate;
  788.     int                    numIndices;
  789.     int                    ni;
  790.     int                    a, b, c;
  791.     int                    indices[MAX_INDICES];
  792.  
  793.     // determine the triangle strip order
  794.     numIndices = ( ds->numVerts - 2 ) * 3;
  795.     if ( numIndices > MAX_INDICES ) {
  796.         Error( "MAX_INDICES exceeded for surface" );
  797.     }
  798.  
  799.     // try all possible orderings of the points looking
  800.     // for a strip order that isn't degenerate
  801.     for ( rotate = 0 ; rotate < ds->numVerts ; rotate++ ) {
  802.         for ( ni = 0, i = 0 ; i < ds->numVerts - 2 - i ; i++ ) {
  803.             a = ( ds->numVerts - 1 - i + rotate ) % ds->numVerts;
  804.             b = ( i + rotate ) % ds->numVerts;
  805.             c = ( ds->numVerts - 2 - i + rotate ) % ds->numVerts;
  806.  
  807.             if ( IsTriangleDegenerate( drawVerts + ds->firstVert, a, b, c ) ) {
  808.                 break;
  809.             }
  810.             indices[ni++] = a;
  811.             indices[ni++] = b;
  812.             indices[ni++] = c;
  813.  
  814.             if ( i + 1 != ds->numVerts - 1 - i ) {
  815.                 a = ( ds->numVerts - 2 - i + rotate ) % ds->numVerts;
  816.                 b = ( i + rotate ) % ds->numVerts;
  817.                 c = ( i + 1 + rotate ) % ds->numVerts;
  818.  
  819.                 if ( IsTriangleDegenerate( drawVerts + ds->firstVert, a, b, c ) ) {
  820.                     break;
  821.                 }
  822.                 indices[ni++] = a;
  823.                 indices[ni++] = b;
  824.                 indices[ni++] = c;
  825.             }
  826.         }
  827.         if ( ni == numIndices ) {
  828.             break;        // got it done without degenerate triangles
  829.         }
  830.     }
  831.  
  832.     // if any triangle in the strip is degenerate,
  833.     // render from a centered fan point instead
  834.     if ( ni < numIndices ) {
  835.         c_fanSurfaces++;
  836.         SurfaceAsTriFan( ds );
  837.         return;
  838.     }
  839.  
  840.     // a normal tristrip
  841.     c_stripSurfaces++;
  842.  
  843.     if ( numDrawIndexes + ni > MAX_MAP_DRAW_INDEXES ) {
  844.         Error( "MAX_MAP_DRAW_INDEXES" );
  845.     }
  846.     ds->firstIndex = numDrawIndexes;
  847.     ds->numIndexes = ni;
  848.  
  849.     memcpy( drawIndexes + numDrawIndexes, indices, ni * sizeof(int) );
  850.     numDrawIndexes += ni;
  851. }
  852.  
  853. /*
  854. ===============
  855. EmitPlanarSurf
  856. ===============
  857. */
  858. void EmitPlanarSurf( mapDrawSurface_t *ds ) {
  859.     int                j;
  860.     dsurface_t        *out;
  861.     drawVert_t        *outv;
  862.  
  863.     if ( numDrawSurfaces == MAX_MAP_DRAW_SURFS ) {
  864.         Error( "MAX_MAP_DRAW_SURFS" );
  865.     }
  866.     out = &drawSurfaces[ numDrawSurfaces ];
  867.     numDrawSurfaces++;
  868.  
  869.     out->surfaceType = MST_PLANAR;
  870.     out->shaderNum = EmitShader( ds->shaderInfo->shader );
  871.     out->firstVert = numDrawVerts;
  872.     out->numVerts = ds->numVerts;
  873.     out->fogNum = ds->fogNum;
  874.     out->lightmapNum = ds->lightmapNum;
  875.     out->lightmapX = ds->lightmapX;
  876.     out->lightmapY = ds->lightmapY;
  877.     out->lightmapWidth = ds->lightmapWidth;
  878.     out->lightmapHeight = ds->lightmapHeight;
  879.  
  880.     VectorCopy( ds->lightmapOrigin, out->lightmapOrigin );
  881.     VectorCopy( ds->lightmapVecs[0], out->lightmapVecs[0] );
  882.     VectorCopy( ds->lightmapVecs[1], out->lightmapVecs[1] );
  883.     VectorCopy( ds->lightmapVecs[2], out->lightmapVecs[2] );
  884.  
  885.     for ( j = 0 ; j < ds->numVerts ; j++ ) {
  886.         if ( numDrawVerts == MAX_MAP_DRAW_VERTS ) {
  887.             Error( "MAX_MAP_DRAW_VERTS" );
  888.         }
  889.         outv = &drawVerts[ numDrawVerts ];
  890.         numDrawVerts++;
  891.         memcpy( outv, &ds->verts[ j ], sizeof( *outv ) );
  892.         outv->color[0] = 255;
  893.         outv->color[1] = 255;
  894.         outv->color[2] = 255;
  895.         outv->color[3] = 255;
  896.     }
  897.  
  898.     // create the indexes
  899.     SurfaceAsTristrip( out );
  900. }
  901.  
  902.  
  903. /*
  904. ===============
  905. EmitPatchSurf
  906. ===============
  907. */
  908. void EmitPatchSurf( mapDrawSurface_t *ds ) {
  909.     int                j;
  910.     dsurface_t        *out;
  911.     drawVert_t        *outv;
  912.  
  913.     if ( numDrawSurfaces == MAX_MAP_DRAW_SURFS ) {
  914.         Error( "MAX_MAP_DRAW_SURFS" );
  915.     }
  916.     out = &drawSurfaces[ numDrawSurfaces ];
  917.     numDrawSurfaces++;
  918.  
  919.     out->surfaceType = MST_PATCH;
  920.     out->shaderNum = EmitShader( ds->shaderInfo->shader );
  921.     out->firstVert = numDrawVerts;
  922.     out->numVerts = ds->numVerts;
  923.     out->firstIndex = numDrawIndexes;
  924.     out->numIndexes = ds->numIndexes;
  925.     out->patchWidth = ds->patchWidth;
  926.     out->patchHeight = ds->patchHeight;
  927.     out->fogNum = ds->fogNum;
  928.     out->lightmapNum = ds->lightmapNum;
  929.     out->lightmapX = ds->lightmapX;
  930.     out->lightmapY = ds->lightmapY;
  931.     out->lightmapWidth = ds->lightmapWidth;
  932.     out->lightmapHeight = ds->lightmapHeight;
  933.  
  934.     VectorCopy( ds->lightmapOrigin, out->lightmapOrigin );
  935.     VectorCopy( ds->lightmapVecs[0], out->lightmapVecs[0] );
  936.     VectorCopy( ds->lightmapVecs[1], out->lightmapVecs[1] );
  937.     VectorCopy( ds->lightmapVecs[2], out->lightmapVecs[2] );
  938.  
  939.     for ( j = 0 ; j < ds->numVerts ; j++ ) {
  940.         if ( numDrawVerts == MAX_MAP_DRAW_VERTS ) {
  941.             Error( "MAX_MAP_DRAW_VERTS" );
  942.         }
  943.         outv = &drawVerts[ numDrawVerts ];
  944.         numDrawVerts++;
  945.         memcpy( outv, &ds->verts[ j ], sizeof( *outv ) );
  946.         outv->color[0] = 255;
  947.         outv->color[1] = 255;
  948.         outv->color[2] = 255;
  949.         outv->color[3] = 255;
  950.     }
  951.  
  952.     for ( j = 0 ; j < ds->numIndexes ; j++ ) {
  953.         if ( numDrawIndexes == MAX_MAP_DRAW_INDEXES ) {
  954.             Error( "MAX_MAP_DRAW_INDEXES" );
  955.         }
  956.         drawIndexes[ numDrawIndexes ] = ds->indexes[ j ];
  957.         numDrawIndexes++;
  958.     }
  959. }
  960.  
  961. /*
  962. ===============
  963. EmitFlareSurf
  964. ===============
  965. */
  966. void EmitFlareSurf( mapDrawSurface_t *ds ) {
  967.     dsurface_t        *out;
  968.  
  969.     if ( numDrawSurfaces == MAX_MAP_DRAW_SURFS ) {
  970.         Error( "MAX_MAP_DRAW_SURFS" );
  971.     }
  972.     out = &drawSurfaces[ numDrawSurfaces ];
  973.     numDrawSurfaces++;
  974.  
  975.     out->surfaceType = MST_FLARE;
  976.     out->shaderNum = EmitShader( ds->shaderInfo->shader );
  977.     out->fogNum = ds->fogNum;
  978.  
  979.     VectorCopy( ds->lightmapOrigin, out->lightmapOrigin );
  980.     VectorCopy( ds->lightmapVecs[0], out->lightmapVecs[0] );    // color
  981.     VectorCopy( ds->lightmapVecs[2], out->lightmapVecs[2] );
  982. }
  983.  
  984.  
  985. /*
  986. ===============
  987. EmitModelSurf
  988. ===============
  989. */
  990. void EmitModelSurf( mapDrawSurface_t *ds ) {
  991.     int                j;
  992.     dsurface_t        *out;
  993.     drawVert_t        *outv;
  994.  
  995.     if ( numDrawSurfaces == MAX_MAP_DRAW_SURFS ) {
  996.         Error( "MAX_MAP_DRAW_SURFS" );
  997.     }
  998.     out = &drawSurfaces[ numDrawSurfaces ];
  999.     numDrawSurfaces++;
  1000.  
  1001.     out->surfaceType = MST_TRIANGLE_SOUP;
  1002.     out->shaderNum = EmitShader( ds->shaderInfo->shader );
  1003.     out->firstVert = numDrawVerts;
  1004.     out->numVerts = ds->numVerts;
  1005.     out->firstIndex = numDrawIndexes;
  1006.     out->numIndexes = ds->numIndexes;
  1007.     out->patchWidth = ds->patchWidth;
  1008.     out->patchHeight = ds->patchHeight;
  1009.     out->fogNum = ds->fogNum;
  1010.     out->lightmapNum = ds->lightmapNum;
  1011.     out->lightmapX = ds->lightmapX;
  1012.     out->lightmapY = ds->lightmapY;
  1013.     out->lightmapWidth = ds->lightmapWidth;
  1014.     out->lightmapHeight = ds->lightmapHeight;
  1015.  
  1016.     VectorCopy( ds->lightmapOrigin, out->lightmapOrigin );
  1017.     VectorCopy( ds->lightmapVecs[0], out->lightmapVecs[0] );
  1018.     VectorCopy( ds->lightmapVecs[1], out->lightmapVecs[1] );
  1019.     VectorCopy( ds->lightmapVecs[2], out->lightmapVecs[2] );
  1020.  
  1021.     for ( j = 0 ; j < ds->numVerts ; j++ ) {
  1022.         if ( numDrawVerts == MAX_MAP_DRAW_VERTS ) {
  1023.             Error( "MAX_MAP_DRAW_VERTS" );
  1024.         }
  1025.         outv = &drawVerts[ numDrawVerts ];
  1026.         numDrawVerts++;
  1027.         memcpy( outv, &ds->verts[ j ], sizeof( *outv ) );
  1028.         outv->color[0] = 255;
  1029.         outv->color[1] = 255;
  1030.         outv->color[2] = 255;
  1031.     }
  1032.  
  1033.     for ( j = 0 ; j < ds->numIndexes ; j++ ) {
  1034.         if ( numDrawIndexes == MAX_MAP_DRAW_INDEXES ) {
  1035.             Error( "MAX_MAP_DRAW_INDEXES" );
  1036.         }
  1037.         drawIndexes[ numDrawIndexes ] = ds->indexes[ j ];
  1038.         numDrawIndexes++;
  1039.     }
  1040. }
  1041.  
  1042. //======================================================================
  1043.  
  1044. /*
  1045. ==================
  1046. CreateFlareSurface
  1047.  
  1048. Light flares from surface lights become 
  1049. ==================
  1050. */
  1051. void CreateFlareSurface( mapDrawSurface_t *faceDs ) {
  1052.     mapDrawSurface_t    *ds;
  1053.     int                    i;
  1054.  
  1055.     ds = AllocDrawSurf();
  1056.  
  1057.     if ( faceDs->shaderInfo->flareShader[0] ) {
  1058.         ds->shaderInfo = ShaderInfoForShader( faceDs->shaderInfo->flareShader );
  1059.     } else {
  1060.         ds->shaderInfo = ShaderInfoForShader( "flareshader" );
  1061.     }
  1062.     ds->flareSurface = qtrue;
  1063.     VectorCopy( faceDs->lightmapVecs[2], ds->lightmapVecs[2] );
  1064.  
  1065.     // find midpoint
  1066.     VectorClear( ds->lightmapOrigin );
  1067.     for ( i = 0 ; i < faceDs->numVerts ; i++ ) {
  1068.         VectorAdd( ds->lightmapOrigin, faceDs->verts[i].xyz, ds->lightmapOrigin );
  1069.     }
  1070.     VectorScale( ds->lightmapOrigin, 1.0/faceDs->numVerts, ds->lightmapOrigin );
  1071.  
  1072.     VectorMA( ds->lightmapOrigin, 2,  ds->lightmapVecs[2], ds->lightmapOrigin );
  1073.  
  1074.     VectorCopy( faceDs->shaderInfo->color, ds->lightmapVecs[0] );
  1075.  
  1076.     // FIXME: fog
  1077. }
  1078.  
  1079. /*
  1080. =====================
  1081. FilterDrawsurfsIntoTree
  1082.  
  1083. Upon completion, all drawsurfs that actually generate a reference
  1084. will have been emited to the bspfile arrays, and the references
  1085. will have valid final indexes
  1086. =====================
  1087. */
  1088. void FilterDrawsurfsIntoTree( entity_t *e, tree_t *tree ) {
  1089.     int                i;
  1090.     mapDrawSurface_t    *ds;
  1091.     int                refs;
  1092.     int                c_surfs, c_refs;
  1093.  
  1094.     qprintf( "----- FilterDrawsurfsIntoTree -----\n");
  1095.  
  1096.     c_surfs = 0;
  1097.     c_refs = 0;
  1098.     for ( i = e->firstDrawSurf ; i < numMapDrawSurfs ; i++ ) {
  1099.         ds = &mapDrawSurfs[i];
  1100.  
  1101.         if ( !ds->numVerts && !ds->flareSurface ) {
  1102.             continue;
  1103.         }
  1104.         if ( ds->miscModel ) {
  1105.             refs = FilterMiscModelSurfIntoTree( ds, tree );
  1106.             EmitModelSurf( ds );        
  1107.         } else if ( ds->patch ) {
  1108.             refs = FilterPatchSurfIntoTree( ds, tree );
  1109.             EmitPatchSurf( ds );        
  1110.         } else if ( ds->flareSurface ) {
  1111.             refs = FilterFlareSurfIntoTree( ds, tree );
  1112.             EmitFlareSurf( ds );                    
  1113.         } else {
  1114.             refs = FilterFaceIntoTree( ds, tree );
  1115. //            if ( ds->shaderInfo->value >= 1000 ) { // ds->shaderInfo->flareShader[0] ) {
  1116.             if ( ds->shaderInfo->flareShader[0] ) {
  1117.                 CreateFlareSurface( ds );
  1118.             }
  1119.             EmitPlanarSurf( ds );        
  1120.         }
  1121.         if ( refs > 0 ) {
  1122.             c_surfs++;
  1123.             c_refs += refs;
  1124.         }
  1125.     }
  1126.     qprintf( "%5i emited drawsurfs\n", c_surfs );
  1127.     qprintf( "%5i references\n", c_refs );
  1128.     qprintf( "%5i stripfaces\n", c_stripSurfaces );
  1129.     qprintf( "%5i fanfaces\n", c_fanSurfaces );
  1130. }
  1131.  
  1132.  
  1133.  
  1134.